#ifndef _INT_RB_TREE_H_
#define _INT_RB_TREE_H_
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */


#if defined(__x86_64) && defined(_LP64)
#define _RB_USE_AUGMENTED_PTR
#endif


//#ifndef _RB_TREE_NODE_DEFINITION_
//#define _RB_TREE_NODE_DEFINITION_
typedef struct Int_RB_Tree_Node {
  
    struct Int_RB_Tree_Node *left,*right,*parent;
    int key;
    void* data;
    void *prop;

#ifndef _RB_USE_AUGMENTED_PTR 
    unsigned color;
#endif
} Int_RB_Tree_Node;

static inline void int_rb_tree_node_init(Int_RB_Tree_Node* node)
{
    node->left=NULL;
    node->right=NULL;
    node->parent=NULL;
    node->key=-10000;
    node->data=NULL;
    node->prop=NULL;
#ifndef _RB_USE_AUGMENTED_PTR
    node->color=0;
#endif
}
//#endif


typedef struct Int_RB_Tree_Trav{
    
    struct Int_RB_Tree* tree;
    Int_RB_Tree_Node* it;
    void (*next)(struct Int_RB_Tree_Trav*);
    void (*prev)(struct Int_RB_Tree_Trav*); 
    void* second;
    int first;
    void* prop;
}Int_RB_Tree_Trav;

void int_rb_tree_next(struct Int_RB_Tree_Trav* trav);
void int_rb_tree_prev(struct Int_RB_Tree_Trav *trav);
static inline void int_rb_tree_trav_init(Int_RB_Tree_Trav* irtt)
{
    irtt->tree=NULL;
    irtt->it=NULL;
    irtt->next=int_rb_tree_next;
    irtt->prev=int_rb_tree_prev;
    irtt->second=NULL;
    irtt->first=-1000;
    irtt->prop=NULL;
}
typedef struct Int_RB_Tree {
    struct Int_RB_Tree_Node *root;
    void* (*find)(struct Int_RB_Tree*,int);
    int (*insert)(struct Int_RB_Tree*,int key,void* data);

    int (*erase)(struct Int_RB_Tree*,int key);

    struct Int_RB_Tree_Trav (*begin)(struct Int_RB_Tree*);
    struct Int_RB_Tree_Trav (*rbegin)(struct Int_RB_Tree*);

    struct Int_RB_Tree_Node *rightmost; 
    unsigned int size;
    void* prop;
}Int_RB_Tree;
struct Int_RB_Tree* int_rb_tree_copy(struct Int_RB_Tree*);
//如果是新插入的值返回1
//如果是覆盖或者失败返回0
int int_rb_tree_insert(struct Int_RB_Tree *tree,int key,void* data);
void int_rb_tree_delete_node(struct Int_RB_Tree*tree,struct Int_RB_Tree_Node* node);
int int_rb_tree_delete_key(struct Int_RB_Tree *tree,int key);
Int_RB_Tree_Node* int_rb_tree_find(struct Int_RB_Tree *tree,int key);
void* int_rb_tree_findn(struct Int_RB_Tree * tree,int key);
struct Int_RB_Tree_Trav int_rb_tree_begin(Int_RB_Tree*);
struct Int_RB_Tree_Trav int_rb_tree_rbegin(Int_RB_Tree*);

static inline void int_rb_tree_init(Int_RB_Tree* irt)
{
    irt->root=NULL;
    irt->find=int_rb_tree_findn;
    irt->insert=int_rb_tree_insert;
    irt->erase=int_rb_tree_delete_key;
    irt->begin=int_rb_tree_begin;
    irt->rbegin=int_rb_tree_rbegin;
    irt->rightmost=NULL;
    irt->size=0;
    irt->prop=NULL;
}
void int_rb_tree_free(struct Int_RB_Tree *tree);
void int_rb_tree_free_value(struct Int_RB_Tree* tree);




// typedef struct RB_Tree_Trav{
//   RB_Tree* tree;
//   RB_Tree_Node* it;
//   void*(*next)(struct RB_Tree_Trav*);
//   void*(*prev)(struct RB_Tree_Trav*);
//   void*(*first)(struct RB_Tree_Trav*);
//   void*(*second)(struct RB_Tree_Trav*); 
//   void* prop;
// }RB_Tree_Trav;






#ifdef __cplusplus
} // extern "C"
#endif /* __cplusplus */


#endif